package com.example.code2022;

/**
 * @author: dangwen
 * @createDate: 2022/4/24
 * 240. 搜索二维矩阵 II
 * 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
 * 每行的元素从左到右升序排列。
 * 每列的元素从上到下升序排列。
 * 1.二分查找法
 * 2.线性查找法
 */
public class P240 {
    public static void main(String[] args) {
        int[][] ints = {{1,4,7,11,15},{2,5,8,12,19},{3,6,9,16,22},{10,13,14,17,24},{18,21,23,26,30}};
        System.out.println(lineSearch(ints, 12));
//        System.out.println(binarySearch(ints, 5));

    }

    // 1.二分查找法
    public static boolean binarySearch(int[][] ints, int target){
        int m = ints.length;
        if (m == 0){
            return false;
        }
        int n = ints[0].length;
        int min = Math.min(m, n);
        // 行递增，列递增，行与行之间不保证递增，查询的时候，先查询行，再查询列，查询的元素为矩阵对角线。
        for (int i = 0; i < min; i++){
            // 先寻找行
            boolean row = findFromRows(ints, i, target);
            // 再寻找列
            boolean col = findFromCols(ints, i, target);
            if (row || col){
                return true;
            }
        }
        return false;
    }

    private static boolean findFromCols(int[][] ints, int col, int target) {
        int lo = col;
        int hi = ints.length - 1;
        while (lo <= hi){
            int mid = lo + ((hi - lo) >> 2);
            if (ints[mid][col] == target){
                return true;
            } else if (ints[mid][col] > target){
                hi = mid - 1;
            }else {
                lo = mid + 1;
            }
        }
        return false;
    }

    private static boolean findFromRows(int[][] ints, int row, int target) {
        int lo = row;
        int hi = ints[0].length - 1;
        while (lo <= hi){
            int mid = lo + ((hi - lo) >> 2);
            if (ints[row][mid] == target){
                return true;
            } else if (ints[row][mid] > target){
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return false;
    }

    // 2.线性查找
    public static boolean lineSearch(int[][] ints, int target){
        int m = ints.length;
        if (m == 0){
            return false;
        }
        int n = ints[0].length;
        int i = m - 1;
        int j = 0;
        while (i > 0 && j < n){
            if (ints[i][j] == target){
                return true;
            } else if (ints[i][j] > target){
                i--;
            } else {
                j++;
            }
        }
        return false;
    }

}
